/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年04月09日
*   描    述：
*
================================================================*/
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
  int val;
  struct ListNode *next;
};

struct ListNode *detectCycle(struct ListNode *head) {
  struct ListNode *slow = head;
  struct ListNode *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (fast == slow) {
      slow = head;
      while (fast != slow) {
        slow = slow->next;
        fast = fast->next;
      }
      return slow;
    }
  }
  return NULL;
}

int main() {
  struct ListNode *currNode = NULL;
  struct ListNode *listA = (struct ListNode *)malloc(sizeof(struct ListNode));

  listA->val = 1;
  listA->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = listA->next;

  currNode->val = 2;
  currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 3;
  currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 4;
  currNode->next = (struct ListNode *)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 5;
  currNode->next = listA->next->next;

  printf("%d\n", detectCycle(listA)->val);
  return 0;
}
